package com.cn.algorithm02.class13;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * @description: 是否为搜索二叉树
 * null属于二叉搜索树
 * 它或者是一个空树，或者是具有以下性质的：左子树不为空，则左子树上所有节点的值均小于根节点的值；右子树不为空，则右
 * 子树上所有的节点均大于右子树
 * */
public class C03_IsBST {
    public static void main(String[] args) {
        int[] arr = {6, 3, 9, 2, 5, 7, 11};

        Nodea head = Nodea.getNodeInstance(arr);
        head.left = null;
        //head.left.left = null;
        Nodea.printTree(head);
        System.out.println(isBST(head));
    }

    public static boolean isBST(Nodea head) {
        if (head == null) return true;
        return process(head).isBST;
    }

    public static Info process(Nodea node) {
        if (node == null) {
            return null;
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int max = node.value;
        if (leftInfo != null) {
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            max = Math.max(max, rightInfo.max);
        }
        int min = node.value;
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
        }
        if (rightInfo != null) {
            min = Math.max(min, rightInfo.min);
        }

        boolean isbst = true;
        if (leftInfo != null && leftInfo.isBST == false) {
            isbst = false;
        }
        if (rightInfo != null && rightInfo.isBST == false) {
            isbst = false;
        }
        if (leftInfo != null && leftInfo.max >= node.value) {
            isbst = false;
        }
        if (rightInfo != null && rightInfo.min <= node.value) {
            isbst = false;
        }

        return new Info(isbst, max, min);

    }

    static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }
}
